1. Field of the Invention
This invention relates to the field of data processing systems. More particularly, this invention relates to data processing systems including branch prediction mechanisms.
2. Description of the Prior Art
It is known to provide data processing systems using a pipelined architecture in which multiple program instructions are subject to different stages of their processing within a sequence of pipeline stages. Instructions are fetched into the pipeline by a prefetch unit. A problem arises with conditional branch instructions which may or may not result in a change of program flow, this being unknown at the point at which they are inserted into the pipeline with subsequent instructions requiring to be fetched before it is actually determined whether or not the conditional branch will or will not be taken.
In order to deal with this situation, which can cause severe performance problems due to the requirement to flush the pipeline, refill the pipeline and restart execution should the incorrect instructions be fetched, it is known to provide branch prediction mechanisms within such data processing systems. Such branch prediction mechanisms seek to predict whether or not a particular conditional branch instruction will or will not be taken. It is known to keep a copy of previous branch behavior and when a new branch is encountered to use this stored record of a preceding number of branch outcomes to look up into a branch prediction memory to determine a prediction as to whether or not the conditional branch instruction just encountered will or will not be taken. Whilst this is an effective technique, it consumes circuit resources in terms of circuit area, cost, power consumption etc. As the patterns of preceding branch outcomes are increased in length in an effort to increase the accuracy of the prediction performed, there is a significant rise in the size of memory required to store the predicted outcomes for each of those possible patterns.
It is common within real life program code to have program loops which are typically executed a large number of times before the loop is exited. Such behavior produces a long sequence of repeated final branch taken outcomes terminated by a branch not taken result as the program drops out of the program loop. It is impractical to provide a branch prediction memory capable of storing a long previous branch outcome history sufficient to capture such loop behavior and yet mispredicting such loop ends nevertheless results in a significant performance impact.